package com.sheng.leetcode.year2025.month10.day13;

import org.junit.Test;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author by ls
 * @date 2025/10/13
 * <p>
 * 2273. 移除字母异位词后的结果数组<p>
 * <p>
 * 给你一个下标从 0 开始的字符串 words ，其中 words[i] 由小写英文字符组成。<p>
 * 在一步操作中，需要选出任一下标 i ，从 words 中 删除 words[i] 。其中下标 i 需要同时满足下述两个条件：<p>
 * 0 < i < words.length<p>
 * words[i - 1] 和 words[i] 是 字母异位词 。<p>
 * 只要可以选出满足条件的下标，就一直执行这个操作。<p>
 * 在执行所有操作后，返回 words 。可以证明，按任意顺序为每步操作选择下标都会得到相同的结果。<p>
 * 字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。例如，"dacb" 是 "abdc" 的一个字母异位词。<p>
 * <p>
 * 示例 1：<p>
 * 输入：words = ["abba","baba","bbaa","cd","cd"]<p>
 * 输出：["abba","cd"]<p>
 * 解释：<p>
 * 获取结果数组的方法之一是执行下述步骤：<p>
 * - 由于 words[2] = "bbaa" 和 words[1] = "baba" 是字母异位词，选择下标 2 并删除 words[2] 。<p>
 * 现在 words = ["abba","baba","cd","cd"] 。<p>
 * - 由于 words[1] = "baba" 和 words[0] = "abba" 是字母异位词，选择下标 1 并删除 words[1] 。<p>
 * 现在 words = ["abba","cd","cd"] 。<p>
 * - 由于 words[2] = "cd" 和 words[1] = "cd" 是字母异位词，选择下标 2 并删除 words[2] 。<p>
 * 现在 words = ["abba","cd"] 。<p>
 * 无法再执行任何操作，所以 ["abba","cd"] 是最终答案。<p>
 * <p>
 * 示例 2：<p>
 * 输入：words = ["a","b","c","d","e"]<p>
 * 输出：["a","b","c","d","e"]<p>
 * 解释：<p>
 * words 中不存在互为字母异位词的两个相邻字符串，所以无需执行任何操作。<p>
 * <p>
 * 提示：<p>
 * 1 <= words.length <= 100<p>
 * 1 <= words[i].length <= 10<p>
 * words[i] 由小写英文字母组成<p>
 */
public class LeetCode2273 {

    @Test
    public void test() {
//        String[] words = {"abba", "baba", "bbaa", "cd", "cd"};
        String[] words = {"a", "b", "c", "d", "e"};
        System.out.println(new Solution().removeAnagrams(words));
    }
}

class Solution {
    public List<String> removeAnagrams(String[] words) {
        // 当前
        List<String> list = new ArrayList<>();
        list.add(words[0]);
        int index = 0;
        for (int i = 1; i < words.length; i++) {
            // 判断 i 和 index 是否为字母异位词，不是的话，加入集合内
            if (!areAnagrams(words[i], words[index])) {
                list.add(words[i]);
                index = i;
            }
        }
        return list;
    }

    public boolean areAnagrams(String a, String b) {
        if (a.length() != b.length()) {
            return false;
        }
        Map<Character, Integer> map = new HashMap<>();
        for (char c : a.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        for (char c : b.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) - 1);
            if (map.get(c) < 0) {
                return false;
            }
        }
        return true;
    }
}
